package com.datastructure.test.towerofhanoiproblem;

import java.util.ArrayList;

public class TowerOfHanoiProblem {

    public static void main(String[] args) {

    }

    public ArrayList<String> getSolution(int n) {
        // write code here
        ArrayList<String> res = new ArrayList<>();
        hanoiTower(n,"left","mid","right",res);
        return res;
    }

    public void hanoiTower(int num, String left, String mid, String right,ArrayList<String> res){
        // 如果只有一个盘
        if(num == 1){
            res.add("move from "+left+" to "+right);
        } else {
            // 如果我们有n >= 2的情况，我们可以看作是两个盘 最下面的盘 上面的所有盘
            // 1. 先把最上面的所有盘A->B,移动的过程会使用到C
            hanoiTower(num - 1, left, right, mid,res);
            // 2. 把最下面的盘 left -> right
            res.add("move from "+left+" to "+right);
            // 3.把B塔的所有盘从 mid -> right,移动过程使用到a塔
            hanoiTower(num-1,mid,left,right,res);
        }
    }
}
